package Prim算法;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author: AirMan
 * @date: 2025/6/7 14:00
 * @description:
 * 题目描述：
 * 在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
 * 不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来。
 * 给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
 * 输入描述：
 * 第一行包含两个整数V和E，V代表顶点数，E代表边数。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
 * 接下来共有E行，每行三个整数v1，v2和val，v1和v2为边的起点和终点，val代表边的权值。
 * 输出描述：
 * 输出联通所有岛屿的最小路径总距离
 * 输入示例
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt();
        int e = sc.nextInt();

        // 邻接矩阵存放
        int[][] graph = new int[v + 1][v + 1];
        for (int i = 0; i <= v; i++) {
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int value = sc.nextInt();
            graph[v1][v2] = value;
            graph[v2][v1] = value;
        }
        int[] parent = new int[v + 1]; // 记录选择的边信息
        Arrays.fill(parent, -1);
        Map<Integer, Boolean> tree = new HashMap<>();   // 生成树中的节点
        int[] miniDistant = new int[v + 1]; // 记录节点到达生成树的距离
        Arrays.fill(miniDistant, Integer.MAX_VALUE);
        // 只需要遍历 v - 1 个节点，以及 e - 1 条边即可
        for (int i = 1; i < v; i++) {
            // 1.选取距离生成树距离最短的节点
            int curNode = 1; // 当前的节点
            int curDistant = Integer.MAX_VALUE; // 当前节点的最小值
            for (int j = 1; j <= v; j++) {
                if (!tree.containsKey(j) && miniDistant[j] < curDistant) {
                    curNode = j;
                    curDistant = miniDistant[j];
                }
            }
            // 2.将该节点加入到生成树中
            tree.put(curNode, true);
            // 3.更新其他还未加入的节点到生成树的距离（更新新加入的节点，它所连接的节点中，这些节点距离生成树的距离是否能够更新）
            for (int j = 1; j <= v; j++) {
                if (!tree.containsKey(j) && graph[curNode][j] < miniDistant[j]) {
                    miniDistant[j] = graph[curNode][j];
                    parent[j] = curNode;
                }
            }
        }
        int result = 0; // 统计最小生成树的总权重
        for (int i = 2; i <= v; i++) {
            result += miniDistant[i];
        }
        System.out.println("总权重：" + result);
        System.out.println("选择的边：");
        // 统计选边情况
        for (int i = 2; i <= v; i++) {
            System.out.println(i + " <--> " + parent[i]);
        }
    }
}
